package HighOrderSortingAlgorithm;

public class QuickSort3_0 {

    //快速排序3.0:时间复杂度O(NlogN):空间复杂度O(logN)
    // 不具备稳定性
    public static void quickSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        quickSort(arr, 0, arr.length - 1);
    }

    public static void swap(int[] arr,int i,int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    // arr[l..r]排好序
    public static void quickSort(int[] arr, int L, int R) {
        if (L < R) {
            swap(arr, L + (int) (Math.random() * (R - L + 1)) , R);
            int[] p = partition(arr, L, R); // 求出 = 区的左右边界
            quickSort(arr, L, p[0] - 1); // < 区
            quickSort(arr, p[1] + 1, R); // > 区
        }
    }

    public static int[] partition(int[] arr, int L, int R) {
        int less = L - 1; // < 区右边界
        int more = R; // > 区左边界
        while (L < more) {
            if (arr[L] < arr[R]) {
                swap(arr, ++less, L++);
            }else if (arr[L] > arr[R]) {
                swap(arr, --more, L);
            }else {
                L++;
            }
        }
        swap(arr, more, R);
        return new int[] {less + 1, more};
    }
}
